package com.example.interview.algorithm;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author gaobing
 * @Description: TODO
 * @date 2018年9月29日 上午9:55:20 思路：算法思想：基于分治的思想，是冒泡排序的改进型。
 * 首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率，后面讲解选取的方法），
 * 然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，
 * 首先从后半部分开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值，
 * 然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换lo和hi位置的值，
 * 如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置。
 * 一次排序就完成了。以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。
 */
public class Test00kuaisupaixu {

    private static void quickSort(int[] arr, int low, int high) {

        if (low > high) {
            return;
        }
        int left, right, temp, swap;
        left = low;
        right = high;
        // temp就是基准位
        temp = arr[low];  //6

        // 6, 1, 9, 3, 2, 7, 8, 4, 5  left=0 right=8
        // 6, 1, 5, 3, 2, 7, 8, 4, 9  left=2 right=8
        // 6, 1, 5, 3, 2, 4, 8, 7, 9  left=5 right=7
        // 6, 1, 5, 3, 2, 4, 8, 7, 9  left=5 right=5 break;

        while (left < right) {
            // 先看右边，依次往左递减
            while (temp <= arr[right] && left < right) {
                right--;
            }
            // 再看左边，依次往右递增
            while (temp >= arr[left] && left < right) {
                left++;
            }
            // 如果满足条件则交换
            if (left < right) {
                swap = arr[left];
                arr[left] = arr[right];
                arr[right] = swap;
            }

        }
        // 最后将基准与i和j相等位置的数字交换
        // 4, 1, 5, 3, 2, 6, 8, 7, 9
        arr[low] = arr[left];
        arr[left] = temp;
        // 递归调用左半数组
        quickSort(arr, low, right - 1);
        // 递归调用右半数组
        quickSort(arr, right + 1, high);

    }

    public static void quickSortCore(int[] arr) {
        if (arr == null || arr.length == 0)
            return;
        quickSort(arr, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        int[] arr = {6, 1, 9, 3, 2, 7, 8, 4, 5,3,-1};

        quickSortCore(arr);

        System.out.println(Arrays.toString(arr));

    }

}
